package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/binary-tree-paths/'>二叉树的所有路径(Binary Tree Paths)</a>
 * <p>给你一个二叉树的根节点 root ，按<b>任意顺序</b>，返回所有从根节点到叶子节点的路径。</p>
 * <p>叶子节点是指没有子节点的节点。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *              1
 *             / \
 *            2   3
 *             \
 *              5
 *      输入：root = [1,2,3,null,5]
 *      输出：["1->2->5","1->3"]
 *
 * 示例 2：
 *      输入：root = [1]
 *      输出：["1"]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目在范围 [1, 100] 内</li>
 *     <li>-100 <= Node.val <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/8 16:36
 */
public class LC0257BinaryTreePaths_S {

    static class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            //return binaryTreePathsByIterator(root);
            //return binaryTreePathsByRecursion1(root);
            return binaryTreePathsByRecursion2(root);
        }

        public List<String> binaryTreePathsByIterator(TreeNode root) {
            List<String> resList = new ArrayList<>();
            if (root == null) {
                return resList;
            }
            Queue<TreeNode> helper = new LinkedList<>();
            Queue<String> path = new LinkedList<>();
            helper.offer(root);
            path.offer("");
            while (!helper.isEmpty()) {
                TreeNode currNode = helper.poll();
                String currPath = path.poll() + currNode.val;
                // 叶子节点
                if (currNode.left == null && currNode.right == null) {
                    resList.add(currPath);
                }
                // 非叶子节点
                else {
                    if (currNode.left != null) {
                        helper.offer(currNode.left);
                        path.offer(currPath + "->");
                    }
                    if (currNode.right != null) {
                        helper.offer(currNode.right);
                        path.offer(currPath + "->");
                    }
                }
            }
            return resList;
        }

        private List<String> binaryTreePathsByRecursion1(TreeNode root) {
            List<String> resList = new ArrayList<>();
            dfs1(root, new StringBuilder(), resList);
            return resList;
        }

        public void dfs1(TreeNode currNode, StringBuilder currPath, List<String> pathList) {
            if (currNode == null) {
                return;
            }
            int length = currPath.length();
            if (currNode.left == null && currNode.right == null) {
                currPath.append(currNode.val);
                pathList.add(currPath.toString());
            } else {
                currPath.append(currNode.val).append("->");
                dfs1(currNode.left, currPath, pathList);
                dfs1(currNode.right, currPath, pathList);
            }
            // 剪枝
            currPath.setLength(length);
        }

        private List<String> binaryTreePathsByRecursion2(TreeNode root) {
            List<String> resList = new ArrayList<>();
            dfs2(root, "", resList);
            return resList;
        }

        public void dfs2(TreeNode currNode, String currPath, List<String> pathList) {
            if (currNode == null) {
                return;
            }
            currPath += currNode.val;
            if (currNode.left == null && currNode.right == null) {
                pathList.add(currPath);
            }
            if (currNode.left != null) {
                dfs2(currNode.left, currPath + "->", pathList);
            }
            if (currNode.right != null) {
                dfs2(currNode.right, currPath + "->", pathList);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);
        Solution solution = new Solution();
        Printer.printListString(solution.binaryTreePaths(root));
    }
}
